package edu.hubu.JosephRing;

import java.util.Scanner;

/*使用链表和面向对象实现约瑟夫环问题*/
public class JosephRingDemo {
    public static void main(String[] args) {
        /*游戏规则：
        游戏开始，从第一个人数起,数到k的人出局；
        游戏继续，从出局的下一个人继续数，数到k的人再出居。
        依次重复下去，直到最后只剩下最后一人，即为胜者*/
        System.out.println("-----游戏开始-----");
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入出局间隔：");
        int k = sc.nextInt();
        System.out.println("请输入游戏人数：");
        int num = sc.nextInt();
        //以4个人为例，1234 : 最先出局的是3，然后剩下412,接着2出局，剩下41，这时候就是4出局，最后剩下1.
        int winnerIndex = count(num, k);
        System.out.println("在以" + k + "为出局间隔，总人数为" + num + "的约瑟夫环游戏中，最后的胜者是：" + winnerIndex);
        System.out.println("-----游戏结束！-----");
    }

    public static int count(int num, int k) {
        //头结点不存储数据
        Node head = new Node();
        Node cur = head;

        //循环构造这个链表
        for (int i = 1; i <= num; i++) {
            Node node = new Node(i);
            cur.nextNode = node;
            cur = node;
        }

        //链表有数据的部分（除头结点）首尾相连形成一个环。
        cur.nextNode = head.nextNode;

        //游戏开始的时候，刨去头结点，从第一个有数据的结点开始报数
        Node p = head.nextNode;
        System.out.println("游戏出局的顺序：");
        //循环退出的条件是最后只剩一个结点（就是这个结点的下一个结点是它本身）
        while (p.nextNode != p) {
            //正常报数的遍历逻辑
            for (int i = 1; i < k - 1; i++) {
                p = p.nextNode;
            }
            //当数到k的时候，出局
            System.out.print(p.nextNode.data + "->");

            //从出局的下一个人继续游戏
            p.nextNode = p.nextNode.nextNode;
            p = p.nextNode;
        }
        //最后剩下的一个结点
        System.out.println("(winner:" + p.data + ")");

        //返回胜者（最后剩下的人）
        return p.data;
    }

}
